/*
https://leetcode-cn.com/problems/find-median-from-data-stream/solution/shu-ju-liu-de-zhong-wei-shu-by-leetcode-ktkst/
 */

import java.util.PriorityQueue;

public class Solution295 {

    PriorityQueue<Integer> queue1;
    PriorityQueue<Integer> queue2;

    public Solution295() {
        queue1= new PriorityQueue<>((a, b) -> (b - a));
        queue2= new PriorityQueue<>((a, b) -> (a - b));
    }

    public void addNum(int num) {
        if (queue1.isEmpty()||num<=queue1.peek()){
            queue1.offer(num);
            if (queue1.size()>queue2.size()+1){
                queue2.offer(queue1.poll());
            }
        }else{
            queue2.offer(num);
            if (queue1.size()<queue2.size()){
                queue1.offer(queue2.poll());
            }
        }
    }

    public double findMedian() {
      if (queue1.size()>queue2.size()){
          return queue1.peek();
      }else{
          return (queue1.peek()+queue2.peek())/2.0;
      }
    }

    public static void main(String[] args) {
        Solution295 solution295=new Solution295();
        solution295.addNum(-1);
        System.out.println(solution295.findMedian());
        solution295.addNum(-2);
        System.out.println(solution295.findMedian());
        solution295.addNum(-3);
        System.out.println(solution295.findMedian());
        solution295.addNum(-4);
        System.out.println(solution295.findMedian());
        solution295.addNum(-5);
        System.out.println(solution295.findMedian());
    }
}
